package william.array;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ZhangShenao
 * @date 2024/3/4
 * @description <a href="https://leetcode.cn/problems/intersection-of-two-arrays/description/">...</a>
 */
public class Leetcode349_两个数组的交集 {
    /**
     * 借助Set实现
     * 首先遍历第一个数组,将所有元素保存在Set中
     * 然后遍历第二个数组,将其中所有包含在Set中的元素,保存到结果Set中
     * <p>
     * 时间复杂度O(N) 对两个数组均遍历一遍
     * 空间复杂度O(N) 使用两个Set保存中间结果
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        //边界条件校验
        if (nums1 == null || nums1.length < 1 || nums2 == null || nums2.length < 1) {
            return new int[0];
        }

        //遍历第一个数组,将所有元素保存在Set中
        Set<Integer> elements = new HashSet<>(nums1.length);
        for (int n : nums1) {
            elements.add(n);
        }

        //遍历第二个数组,将其中所有包含在Set中的元素,保存到结果Set中
        Set<Integer> intersection = new HashSet<>(nums2.length);
        for (int n : nums2) {
            if (elements.contains(n)) {
                intersection.add(n);
            }
        }

        //将结果转换成数组返回
        int[] result = new int[intersection.size()];
        int i = 0;
        for (int n : intersection) {
            result[i++] = n;
        }
        return result;
    }
}
